package YuanFuDao2;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的宽度: 求每层多少个节点
 */
public class Main8 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(3);
        head.left = new TreeNode(7);
        head.right = new TreeNode(7);
        head.left.left = new TreeNode(6);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(5);
        head.right.right = new TreeNode(6);
        //head.left.left.left = new TreeNode(9);
        System.out.println(treeHeight(head));
//        System.out.println("节点数: " + getKNums(head,3));
        //head.left.left.right = new TreeNode(16);
        //System.out.println(help(head));
//        if(head == null){
//            System.out.println(true);
//        }else{
//            System.out.println(help2(head.left,head.right));
//        }

//        int[] arr = {3,1,6,4,8,9,18,0};
//        TreeNode node = new TreeNode(arr[0]);
//        for (int i = 1; i < arr.length; i++) {
//            buildBinarySearchTree(node,arr[i]);
//        }
//        InOrder(node);
    }

    public static int help(TreeNode head){
        if(head == null) return 0;
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        int curCountInQueue = 1;//二叉树当前层已经存在队列中的个数
        int res = 0;  //节点数最大的层的节点数
        while(!queue.isEmpty()){
            curCountInQueue--;
            if (curCountInQueue == 0) {
                res = Math.max(res, queue.size());
                curCountInQueue = queue.size();
            }

            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        return res;
    }


    // 判断一个二叉树是否对称
    public static boolean help2(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;
        return root1.val == root2.val && help2(root1.left,root2.right) && help2(root1.right,root2.left);
    }



    // 二叉树第k层节点数
    public static int getKNums(TreeNode head,int k){
        if(head == null || k < 1) return 0;
        if(k == 1) return 1;
        return getKNums(head.left,k-1) + getKNums(head.right,k-1);
    }

    public static boolean isSearchTree(TreeNode head){  // 判断一棵树是否是二叉搜索树
        if(head == null) return true;

        Queue q = new LinkedList();

        List x = new LinkedList();
        

        return true;
    }

    // 无序数组构建一棵二叉排序树
    public static TreeNode buildBinarySearchTree(TreeNode node,int i){
        if(node==null){
            node = new TreeNode(i);
            return node;
        }else {
            if(node.val > i){
                node.left = buildBinarySearchTree(node.left,i);
            }else{
                node.right = buildBinarySearchTree(node.right,i);
            }
            return node;
        }
    }

    public static void InOrder(TreeNode node){
        if(node == null) return;
        InOrder(node.left);
        System.out.print(node.val + " ");
        InOrder(node.right);
    }


    // 不使用递归求二叉树的深度
    public static int treeHeight(TreeNode head){
/*
        // 递归
        if(head == null) return 0;
        return Math.max(treeHeight(head.left),treeHeight(head.right))+1;
*/
        if(head==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int height = 0;
        queue.add(head);
        while(!queue.isEmpty()){
            int len = queue.size();
            height++;
            while(len > 0){
                TreeNode node = queue.poll();
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                len--;
            }
        }

        return height;
    }





}





class TreeNode{

    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }





}
